package sort;

public class ShellSort {

    public static void main(String[] args) {
        int[] nums = new int[]{1,5,8,2,3,9,4};
        System.out.println("从小到大排序后的结果是:");
        int[] numbers = shell(nums);
        for(int i=0;i<numbers.length;i++){
            System.out.print(numbers[i]+" ");
        }
    }

    /**
     * 假设有数组：{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9}
     * 此时 n = 10
     * 1.一般情况下，我们取increment为：10/2 = 5,则此时：{a0,a5}、{a1,a6}、{a2,a7}、{a3,a8}、{a4,a9}这五组就是该数组的子序列,分别对这些子序列进行插入排序。
     * 2.我们再取increment为：5/2 = 2，则此时：{a0,a2,a4,a6,a8}和{a1,a3,a5,a7,a9}这两组就是该数组的子序列,分别对这两个序列进行插入排序。
     * 3.我们再取increment为：2/1 = 1,则此时：{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9}所有元素都在同一个子序列中。
     * 4.此时对其进行插入排序，因为有前面的工作基础，大多数元素已经基本有序，所以排序速度仍然很快。
     * 从上面我们可以看到，增量increment是在逐渐减小的，所以这个方法我们也叫它为：缩小增量排序。
     * @param nums
     * @return
     */
    public static int[] shell(int[] nums){
        int n = nums.length;
        int increment = n/2;
        for(;increment>0;increment/=2) {
            int i = increment;
            for(;i<nums.length;i++) {
                int temp = nums[i];
                int t = i-increment;
                while(t >= 0 && nums[t] > temp) {
                    nums[i] = nums[t];
                    t -= increment;
                }
                nums[t+increment] = temp;
            }
        }
        return nums;
    }

}
